package main

import "fmt"

//#link: https://leetcode-cn.com/problems/longest-palindromic-substring/
func main() {
	s := "bb"
	fmt.Println(longestPalindrome(s))
}

/**
 * @Description: 给你一个字符串 s，找到 s 中最长的回文子串。
 */
func longestPalindrome(s string) string {

	if len(s) < 2 {
		return s
	}
	start, maxLen := 0, 1
	sBytes := []byte(s)
	l := len(sBytes)
	dp := make([][]bool, l)
	//单个字符肯定是回文串
	for i := 0; i < l; i++ {
		dp[i] = make([]bool, l)
		dp[i][i] = true
	}
	//从2个字符开始计算
	for left := 2; left <= l; left++ {
		for i := 0; i < l; i++ {
			//计算有边界
			j := left + i - 1
			//若有边界超出界限，则结束
			if j >= l {
				break
			}
			//若两个字母不相等，则肯定不是回文串
			if sBytes[i] != sBytes[j] {
				dp[i][j] = false
			} else {
				if j-i < 3 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}
			//当是回文串时，并且长度大于最大长度，修改开始下标和最大长度
			if dp[i][j] && (j-i+1) > maxLen {
				start = i
				maxLen = j - i + 1
			}
		}
	}
	return s[start : start+maxLen]
}
